/*
 * @lc app=leetcode.cn id=309 lang=swift
 *
 * [309] 最佳买卖股票时机含冷冻期
 */

// @lc code=start
class Solution309 {
    // 定义三种状态
    // 1. 持有一只股票
    // 2. 不持有任何股票，并且处于冷冻期
    // 3. 不持有任何股票，且非冷冻期
    // 写递推表达式特别注意状态是怎么而来的；
    // 代码随想录里对这个题解释的不是很清楚；
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count == 0 {
            return 0
        }
        let n = prices.count
        let array = Array(repeating: 0, count: 3)
        var dp = Array(repeating: array, count: n)
        // 初始化
        dp[0][0] = -prices[0]
        // 状态转移
        for i in 1..<n {
            // 持有一只股票：可以本来就持有，可以是非冷冻期购买股票
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i])
            // 不持有股票，并且处于冷冻期：只能是由持有股票并且卖出获得
            dp[i][1] = dp[i - 1][0] + prices[i]
            // 不持有股票，且非冷冻: 可以由原本就是这样，可以是上次冷冻而来
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2])
        }
        return max(dp[n - 1][1], dp[n - 1][2])
    }
    static func test() {
        let array = [1,2,3,0,2]
        let restu = Solution309().maxProfit(array)
        print(restu)
    }
}
// @lc code=end

